\documentclass[12pt]{article}
\usepackage{amsfonts,amsmath,amssymb,graphicx,url}
\usepackage{fullpage}


% Old Stuff
%%\oddsidemargin=0.15in
%%\evensidemargin=0.15in
%%\topmargin=-.5in
%%\textheight=9in
%%\textwidth=6.25in

\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6.25in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\heading}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 6.2in { {\bf CS390 Computational Game Theory and Mechanism Design}
     	 \hfill #2 }
       \vspace{4mm}
       \hbox to 6.2in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 6.2in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\handout}[3]{\heading{#1}{#2}{Instructor:
Jing Chen}{Teaching Assistant: Tao Xiao}{Handout #1: #3}}

\setlength{\parindent}{0in}
\setlength{\parskip}{0.1in}

\begin{document}
\handout{5}{July 10, 2013}{Problem Set 4}

%This course is an undergraduate introduction to computational game theory, with emphasis on mechanism design.

\textbf{Due by Wednesday, July 17, 2pm.}

\paragraph{Problem 1 (10pt).} For any small constant $\epsilon$, find an $\epsilon$-Nash equilibrium that is not a Nash equilibrium, in the 6-player star-shape matching pennies game introduced in class.

\paragraph{Problem 2 (10pt).} Work out the algorithm TreeNash for the same game in Problem 1. That is, write out (or give compact description) of all the tables and witness lists generated by the algorithm. Then describe all the NEs of this game, following the top-down procedure.

\paragraph{Problem 3 (10pt).} Prove that for any finite game $G$, any finite convex combination of CEs is still a CE of $G$.
(If $\sigma^1, \dots, \sigma^k\in \Delta(S)$, and if $\lambda_1, \dots, \lambda_k$ are non-negative reals with $\sum_i \lambda_i = 1$, then the convex combination of $\sigma^1,\dots, \sigma^k$ under $\lambda_1, \dots, \lambda_k$ is the distribution $\lambda_1 \sigma^1 + \cdots + \lambda_k \sigma^k$.)

Notice that this problem is related to Proposition 46.2 of OR94. The notion of CE is defined in OR94 in a  way different from ours, but the two definitions are equivalent. One way to solve this problem is to understand the definition in OR94 and its relation with ours, and then rewrite their proof of Proposition 46.2 under our definition.


%
%\paragraph{Problem 2 (10pt).} %122ps.pdf 5
%Consider the following two-state game. In the first stage, player 1 chooses $a\in [0,3]$ and pays player 2 $a/9$ (so that player 1 gets a utility of $-a/9$ and player 2 gets a utility of $a/9$. In the second stage, players 1 and 2 play a simultaneous move game which provides them with the additional utility shown below. What is the subgame perfect equilibrium? What is player 1's equilibrium utility?
%
%\begin{center}
%\begin{tabular}{c|c|c|}
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%\multicolumn{1}{c}{} & \multicolumn{1}{c}{$\ L\ $} & \multicolumn{1}{c}{$\ R\ $}  \\ \cline{2-3}
% & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
%  $U$                  & $1+a, 0$                     & $0, 1$                     \\ [1ex] \cline{2-3}
% & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
%  $D$                  & $0, 1$                     & $1, 0$                     \\ [1ex] \cline{2-3}
%\end{tabular}
%\end{center}

%M. J. Osborne and A. Rubinstein. {\em A course in game theory.} MIT Press, 1994.
%
%N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (eds). {\em Algorithmic game theory.} Cambridge University Press, 2007. (Available at \url{http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf}.)

\end{document}








